package com.Oct_Sixteen;

/**
 * 329. 矩阵中的最长递增路径
 * 给定一个 m x n 整数矩阵 matrix ，找出其中 最长递增路径 的长度。
 *
 * 对于每个单元格，你可以往上，下，左，右四个方向移动。 你 不能 在 对角线 方向上移动或移动到 边界外（即不允许环绕）。
 *
 *  
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/longest-increasing-path-in-a-matrix
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 *
 *2022/10/16 23:28
 */

public class Solution329 {

    /**
     * dfs+记忆化搜索
     * @param matrix
     * @return
     */
    public int longestIncreasingPath(int[][] matrix) {
        int res=0;
        int[][] visted=new int[matrix.length][matrix[0].length];
        for (int i=0;i<matrix.length;i++)
        {
            for (int j=0;j<matrix[0].length;j++)
            {
                res=Math.max(res,dfs(matrix,i,j,visted,Integer.MIN_VALUE));
            }
        }
        return res;
    }

    int dfs(int[][] matrix,int i,int j,int[][] visited,int pre){
        if (i<0||i>=matrix.length||j<0||j>=matrix[0].length||matrix[i][j]<=pre) return 0;
        if (visited[i][j]!=0) return visited[i][j];
        int l=dfs(matrix,i-1,j,visited,matrix[i][j]);
        int r=dfs(matrix,i+1,j,visited,matrix[i][j]);
        int u=dfs(matrix,i,j-1,visited,matrix[i][j]);
        int d=dfs(matrix,i,j+1,visited,matrix[i][j]);
        visited[i][j]=1+Math.max(Math.max(l,r),Math.max(u,d));
        return visited[i][j];
    }

    public static void main(String[] args) {
        Solution329 solution329=new Solution329();
        System.out.println(solution329.longestIncreasingPath(new int[][]{{9,9,4},{6,6,8},{2,1,1}}));
    }

}
